package fun.coding.leetcode;

public class AddBinary {

	public static void main(String[] args) {
		AddBinary ab = new AddBinary();
		System.out.println(ab.addBinary("11", "1"));
		System.out.println(ab.addBinary("11", "11"));
		System.out.println(ab.addBinary("1111111", "11"));
		System.out.println(ab.addBinary("1110111", "1"));
	}
	
	
	// This is definitely a better solution, and it can be easily extended to HEX or others since it is mathematical now.  
	// http://fisherlei.blogspot.com/2013/01/leetcode-add-binary.html
		
	public String addBinary(String a, String b) {
		if (a == null || b == null) return null;
		
		StringBuilder sb = new StringBuilder();
		
		int i = a.length() - 1;
		int j = b.length() - 1;
		int carry = 0;
		while (i >= 0 || j >= 0) {
			int av = (i >=0 ? a.charAt(i) - '0' : 0);
			int bv = (j >=0 ? b.charAt(j) - '0' : 0);
			
			// This is where HEX could be supported. 
			int value = (av + bv + carry) % 2;
			carry = (av + bv + carry) / 2;
			sb.append(value);
			
			i--;
			j--;
		}
		
		if (carry != 0) {
			sb.append(1);
		}
		
		return sb.reverse().toString();
	}
	
	public String addBinaryOld(String a, String b) {
		if (a == null || b == null) return null;
		
		StringBuilder sb = new StringBuilder();
		
		int i = a.length() - 1;
		int j = b.length() - 1;
		
		boolean isCarry = false;
		
		while (i >= 0 && j >= 0) {
			char ac = a.charAt(i);
			char bc = b.charAt(j);
			
			if (ac == '1' && bc == '1') {
				sb.append(isCarry ? 1 : 0);
				isCarry = true;
			} else if (ac == '0' && bc == '0') {
				sb.append(isCarry ? 1 : 0);
				isCarry = false;
			} else {
				sb.append(isCarry ? 0 : 1);
			}
			
			i--;
			j--;
		}
		
		while (j >= 0) {
			char bc = b.charAt(j);
			if (isCarry) {
				if (bc == '0') {
					sb.append(1);
					isCarry = false;
				} else {
					sb.append(0);
				}
				
			} else {
				sb.append(bc);
			}
			j--;
		}
		

		while (i >= 0) {
			char ac = a.charAt(i);
			if (isCarry) {
				if (ac == '0') {
					sb.append(1);
					isCarry = false;
				} else {
					sb.append(0);
				}
				
			} else {
				sb.append(ac);
			}
			i--;
		}
		
		if (isCarry) sb.append(1);
		
		return sb.reverse().toString();
	}
	
}
